import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    private int preIndex;

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildChildTree(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildChildTree(int[] preorder, int[] inorder, int begin, int end){
        if (begin > end){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex]);


        int rootIndex = findIndex(inorder, begin, end, preorder[preIndex]);
        preIndex++;

        root.left = buildChildTree(preorder, inorder, begin, rootIndex - 1);
        root.right = buildChildTree(preorder, inorder, rootIndex + 1, end);

        return root;
    }

    private int findIndex(int[] inorder, int begin, int end, int k){
        for (int i = begin; i <= end; i++){
            if (inorder[i] == k){
                return i;
            }
        }

        return -1;
    }

/*    public int postIndex = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;

        return buildChildTree(postorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildChildTree(int[] postorder, int[] inorder, int begin, int end){
        if (begin > end){
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIndex]);

        int rootIndex = findIndex(inorder, begin, end, postorder[postIndex]);
        postIndex--;

        root.right = buildChildTree(postorder, inorder, rootIndex + 1, end);
        root.left = buildChildTree(postorder, inorder, begin, rootIndex - 1);

        return root;
    }

    private int findIndex(int[] inorder, int begin, int end, int k){
        for (int i = begin; i <= end; i++){
            if (inorder[i] == k){
                return i;
            }
        }

        return -1;
    }*/


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }

        if (p == root || q == root){
            return root;
        }

        TreeNode leftSearch = lowestCommonAncestor(root.left, p ,q);
        TreeNode rightSearch = lowestCommonAncestor(root.right, p ,q);

        if (leftSearch != null && rightSearch != null){
            return root;
        }else if (leftSearch != null){
            return leftSearch;
        }else{
            return rightSearch;
        }
    }


    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null){
            return null;
        }

        queue.offer(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size != 0){
                TreeNode top = queue.poll();

                if (top.left != null){
                    queue.offer(top.left);
                }

                if (top.right != null){
                    queue.offer(top.right);
                }
                list.add(top.val);
                size--;
            }
            ret.add(list);
        }

        return ret;
    }
}

class Main{
    public static void main(String[] args) {

    }
}